package com.LeeCode;

/**
 * 最美子字符串的数目
 */

public class Code1915 {
    public static void main(String[] args) {
        String word = "aa";
        System.out.println(new Code1915().wonderfulSubstrings(word));
    }

    public long wonderfulSubstrings(String word) {
        char[] chars = word.toCharArray();
        int[] cnt = new int[1024];
        cnt[0] = 1;

        long ans = 0;
        int preXor = 0;
        for (int i = 0; i < chars.length; i++) {
            preXor ^= 1 << (chars[i] - 'a');
            // 0个奇数
            if (cnt[preXor] != 0) {
                ans += cnt[preXor];
            }

            // 1个奇数
            for (int j = 0; j < 10; j++) {
                int temp = preXor ^ (1 << j);
                if (cnt[temp] != 0) ans += cnt[temp];
            }

            cnt[preXor]++;
        }
        return ans;
    }
}
